class HashTable {
  constructor() {
    this.storage = [];// 数组存储元素
    this.count = 0;// 记录已经存放了多少元素
    this.limit = 7;// 一共可以放多少个元素
  }

  hashFunc(str, limit) {
    // 传入字符串返回一个下标 比如name
    let hashCode = 0;
    for (let i = 0; i < str.length; i++){
      hashCode = 31 * hashCode + str.charCodeAt(i);
    }
    hashCode = hashCode % limit;
    return hashCode;
  }

  // 放入/修改元素:hashmap->{key,value}
  put(key, value){
    // 1.根据key映射到index
    const index = this.hashFunc(key, this.limit);
    // 注意每个index对应的是一个数组或者链表
    // 2.取出数组
    let bucket = this.storage[index];
    if (bucket === undefined) {
      bucket = []
      this.storage[index] = bucket;
    }
    // 注意key重复的时候会进行覆盖
    // 3.判断是插入还是修改操作
    let overide = false;
    for (let i = 0; i < bucket.length; i++) {
      // js中没有元素概念,这里就是一个数组['name',ldf]
      let tuple = bucket[i];
      if(tuple[0] === key) {
        tuple[1] = value;
        overide = true;
      }
    }
    // 4. 如果没有覆盖就是新增
    if (!overide) {
      bucket.push([key, value]);
      this.count++;
      if (this.count > this.limit * 0.75) {
        let newLimist = this.limit * 2
        newLimist = this.getPrime(newLimist)
        this.resize(newLimist)
      }
    }
  }

  // 根据key值获得value
  get(key) {
    // 1.根据key获得index
    const index = this.hashFunc(key, this.limit)
    // 2.获得bucket
    const bucket = this.storage[index]
    if (bucket === undefined) {return null}
    // 3. 遍历bucket查找
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        return tuple[1];
      }
    }
    return null;
  }

  // 根据key删除元素
  remove(key) {
    //1.key获取index
    const index = this.hashFunc(key, this.limit);
    //2.获取bucket
    const bucket = this.storage[index]
    if (bucket === undefined) {return null}
    for (let i = 0; i < bucket.length; i++){
      let tuple = bucket[i];
      if(tuple[0] === key){
        bucket.splice(i, 1)
        this.count--;
        return tuple[1];
        if(this.limit > 8 && this.count < this.limit*  0.25){
          let newLimist = Math.floor(this.limit / 2)
          newLimist = this.getPrime(newLimist)
          this.resize(newLimist)
        }
      }
    }
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }

  // 扩容函数
  resize(newLimit) {
    // 1. 保存旧的数组中的内容
    let oldStorage = this.storage;
    // 2.重置属性
    this.limit = newLimit;
    this.storage = [];
    this.count = 0;
    // 3.取出oldStorage中的所有元素，重新放入storage
    oldStorage.forEach((bucket) => {
      if (bucket === null) {return}
      for (let i = 0;i < bucket.length; i++) {
        let tuple = bucket[i];
        this.put(tuple[0], tuple[1])
      }
    })
  }

  isPrime(num){
    for(let i = 2; i < num; i++){
      if (num % i == 0){
        return false;
      }
    }
    return true
  }

  getPrime(num) {
    while(!this.isPrime(num)){
      num++
    }
    return num;
  }
}

const hashTable = new HashTable()
hashTable.put('name', 'ldf')
hashTable.put('name','zj')
hashTable.put('age','18')
console.log(hashTable.storage[7]);
console.log(hashTable.get('name'));